/****************************************
* 上机作业2
* 编写含有多个函数的程序实现一元多项式的加法运算。
* 要求先输入两个一元多项式；然后建立对应的链表；
* 再实现加法运算；最后输出新的多项式。
*************************************************/

#include<stdio.h>
#include<malloc.h>
#include<string.h>

int debug = 0;

struct NODE;
typedef struct NODE node;
struct NODE{int exp,coef;node* next;};

void print_poly_desc(const node* p){
    int flag = 0;
    p = p->next;
    while(p){if(flag++&&p->coef>0)putchar('+');printf("%dx^%d",p->coef,p->exp);p=p->next;}putchar('\n');
}

void add_value(node* h,int coef,int exp){
    while(1){
        if(NULL == h->next || h->next->exp < exp){
            if(debug)printf("Add node(coef=%d exp=%d)\n",coef,exp);
            node* p = malloc(sizeof(node));
            p->exp = exp;
            p->coef = coef;
            p->next = h->next;
            h->next = p;
            return;
        }
        if(h->next->exp==exp){h->next->coef += coef;return;}
        h = h->next;
    }
}


// read a string from stdin, parse the polynomial expression 
// and returns a pointer of the first element
// if you use a virtual head node, point its "next" to what this function returns
// for simplification, every mono string must br in form:  
// [+|-] (int) x^ [+|-](int) 
// e.g. f(x)=x is expressed as:  +1x^+1
// f(x) = -x^100 + 99x^-100 + 2 is -1x^+100 + 99x^-100 + 2x^+0
node* read_parse_build_poly(){

    char buf;
    node head;
    node* h = &head;
    h->next = NULL;

    int neg = 0;    // 正在读入的数字是不是负数
    int number = 0; // 正在读入的数字
    int coef = 0;   // 保存coef
    int done = 2;   // 记录一轮读取是否完成 [+|-] (int) x^ [+|-](int) 
    
    while( '\n' != (buf=getchar()) ){
        switch(buf){
            case '0'...'9':
                number*=10; number+=buf-'0'; if(debug){printf("Read integer %c, Number=%d\n",buf,number);} break;
            case 'x':
                coef = number * (neg?-1:1);number=0;neg=0; if(debug){printf("Encountered x^.\n");} break;
            case '-':case '+':
                if(done--){neg=(buf=='-');break;} // omit first '+'/'-'
                number *= (neg?-1:1);
                if(debug)printf("\nadd_value coef=%d number=%d \n\n",coef,number);
                add_value(h,coef,number);
                neg = (buf=='-'); number = 0; done = 1;
                break;
        }
        if(debug)printf("buf= %c neg=%d number=%d coef=%d done=%d\n",buf,neg,number,coef,done);
    }
    number *= (neg?-1:1);
    if(debug)printf("\nadd_value coef=%d number=%d \n\n",coef,number);
    add_value(h,coef,number);
    return h->next;
}

// add b to a
void add_poly(node* ha,node* hb){ 
    hb = hb->next;
    node* p;

    while(1){
        if(ha->next->exp > hb->exp)ha=ha->next;
        if(ha->next->exp < hb->exp){
            p = hb->next;
            hb->next = ha->next;
            ha->next = hb;
            ha = hb;
            hb = p;
        }
        if(ha->next->exp == hb->exp){
            p = hb->next;
            ha->next->coef += hb->coef;
            free(hb);
            hb = p;
            if(ha->next->coef==0){
                p = ha->next;
                ha->next = p->next;
                free(p);
            }
        }
        if(hb==NULL)break;
    }
    
}


int main(int argc,char** argv){
    if(argc==2&& ( strcmp(argv[1],"-d")==0||strcmp(argv[1],"--debug")==0))debug=1;

    node head_a;
    node* ha = &head_a;
    printf("Enter first expression: ");
    ha->next = read_parse_build_poly();
    printf("read expression: ");
    print_poly_desc(ha);

    node head_b;
    node* hb = &head_b;
    printf("Enter second expression: ");
    hb->next = read_parse_build_poly();
    printf("read expression: ");
    print_poly_desc(hb);

    add_poly(ha,hb);

    printf("Added expression: ");
    print_poly_desc(ha);

    // clean-up
    while(ha){hb = ha;ha=ha->next;free(hb);}
    return 0;
}